#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void swap(vector<int> &num, int i, int j)
{
    int tmp = num[i];
    num[i] = num[j];
    num[j] = tmp;
}

void permuteHelper2(vector<int> &num, int index, set<vector<int> > &ans)
{
    if (index == num.size()){
        ans.insert(num);
        return;
    }

    for (int i = index; i < num.size(); i++) {
        if (i!=index && num[i] == num[i-1]) continue;
        swap(num, index, i);
        permuteHelper2(num, index+1, ans);
        swap(num, index, i);
    }
}

class Solution2 {
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());                        
            vector<vector<int> > result;
            set<vector<int> > ans;
            permuteHelper2(num, 0, ans);
            for (set<vector<int> >::iterator iter = ans.begin(); iter != ans.end(); iter++)
                result.push_back(*iter);
            return result;
        }
};

void permuteHelper(vector<int> &num, int index, vector<bool> &used, vector<vector<int> > &ans, vector<int> &cur)
{
    if (index == num.size()){
        ans.push_back(cur);
        return;
    }

    for (int i = 0; i < num.size(); ) {
        if (used[i]){i++; continue;}
        used[i] = true;
        cur.push_back(num[i]);
        permuteHelper(num, index+1, used, ans, cur);
        cur.pop_back();
        used[i] = false;
        int j = i;
        while(i < num.size() && num[i] == num[j]) i++;
    }
}

class Solution {
    public:
        vector<vector<int> > permuteUnique(vector<int> &num) {
            sort(num.begin(), num.end());                        
            vector<vector<int> > ans;
            vector<int> cur;
            vector<bool> used(num.size(), false);
            permuteHelper(num, 0, used, ans, cur);
            return ans;
        }
};

int main(int argc, char **argv)
{
    Solution mySolution;
    vector<int> nums;
    nums.push_back(0);
    nums.push_back(1);
    nums.push_back(0);
    nums.push_back(0);
    nums.push_back(9);
    vector<vector<int> > result = mySolution.permuteUnique(nums);
    for (int i = 0; i < result.size(); i++) {
        for (int j = 0; j < result[i].size(); j++)
            cout << result[i][j] << " " ;
        cout << endl;
    }

    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
